The Fast Walsh Transform (FWT), or Hadamard transform, has been applied to the fields of signal processing, pattern recognition, and communication theory ("Proc. Symp. Appl. Walsh Functions", Naval Res. Lab., Wash., D.C., 1970; "Proc. Symp. Appl. Walsh Functions", Naval Res. Lab., Wash. D.C., 1971; "Sequency filters based on Walsh functions for signals with two space variables", in Proc. 4th Hawaii Int. Conf. Syst. Sci., Univ. Hawaii, Honolulu, pp 414-416, 1971). The following U.S. Patents also relate to Walsh Transforms.
______________________________________ 3,879,605 Special purpose hybrid Carl, Joseph W.; computer to implement Swartwood, Richard V Kronecker matrix transform 3,956,619 Pipeline Walsh-Hadamard Mundy, Joseph L.; transform Joynson, Reuben E. 4,357,677 Hadamard converter Rebourg, Jean-Claude employing charge transfer devices 4,389,673 Hadamard transformer using Despois, Claude; charge transfer devices Rebourg, Jean-Claude 4,446,530 Fast Hadamard transform Tsuboka, Eiichi device 4,525,798 Apparatus for performing a Rebourg, Jean-Claude Hadamard transform Despois, Claude ______________________________________
Due to its orthogonality property, the Walsh transform is well suited for code division multiple access (CDMA) applications, such as cordless phone systems or wireless mobile communications.
The FWT can be used for frequency estimation in lieu of the traditional Fast Fourier Transform (FFT) (See, e.g. U.S. patent application Ser. No. 08/477,863, entitled Estimation of Frequency in Digital Signals Using Fast Walsh Transform, filed on Mar. 14, 1994 for Chun-Chian Lu and assigned to the assignee hereof).
The FWT process can offer greater speed and simpler hardware implementation than the FFT techniques (see, e.g., Harmuth, H. F. "Transmission of Information by Orthogonal Functions", New York, Springer, 1969; "Survey of analog sequency filters based on Walsh functions", in Proc. Symp. Appl. Walsh Functions, Naval Res. Lab., Wash., D.C., pp 208-219, 1970; Wishner, H. D., "Designing a special purpose digital image processor", Computer Design, vol. 11, pp 71-76, February 1972).
Many of the prior FWT implementations were based on Good's factorization of the Hadamard matrix (Good, I. J., "The interaction algorithm and practical Fourier analysis", J. Roy, Statist. Soc., London, vol. B20, 1958). Good's factorization reduced the required number of additions and subtractions from N(N-1) to Nlog2N, but still involved complex signal flow patterns (Yuen, C. K., Remarks on the ordering of Walsh function", IEEE Trans. Computer C-21, 1452, 1972). Other variations on Good's matrix offered simplified computation (Geadah, Y. A., and M. J. G. Corinthios, "Natural, dyadic and sequency order algorithms and processors for the Walsh-Hadamard transform", IEEE Trans. Computer C-26, 435-442, 1977), reduction of interconnection lines (Joseph, W. C., and V. S. Richard, "A hybrid Walsh transform computer", IEEE Trans. on Computer C-22, July 1973), parallel implementation (Elliot, A. R., and Y. Y. Shum, "A parallel array hardware implementation of the fast Hadamard and Walsh transforms", Proc. Symp. Appl. Walsh Functions, Wash. D.C., pp 181-183, 1972), serial implementation (Muniappan, K., and R. Kitai, "Walsh spectrum measurement in natural, dyadic, and sequency ordering", IEEE Trans. Electromag. Compat. EMC-24, 46-49, 1982), and perfect shuffle and the combined adder/subtractor (Shirata K., and M. Nakatsuyama, "The fast Walsh-Hadamard transform and processors by using new permutation networks", Trans. IECE Jpn. J63-D, 319-325, 1980, and also Nakatsuyama, M., and N. Nishizuka, "The fast Walsh-Hadamard transform and processors by using delay lines", Trans. IECE Jpn. E64, 708-715, 1981). Still other methods have used microprocessor, ROM, RAM, PLA, CCD, or SAW devices to perform the Walsh-Hadamard process.
All of the aforementioned techniques have had some limiting disadvantage, either in speed, or hardware complexity, or specific device implementation. For example, the prior method of parallel implementation used N (dimension of the FWT) adder and subtractor units, and the interconnections between the multiplexer and adder were very complex. The prior serial method used fewer adder and subtractor units, but required increased computation time. The perfect shuffle and adder/subtractor (A/S) techniques reduced the number of A/S units from pN to pN/2, where p is the 2's power of N. But, the controller circuit was very complicated, and the output speed was limited to one point at a time.
In view of the foregoing, it is an object of the invention to provide an FWT processor which reduces the number of A/S units from the prior art (pN/2) to (N/2). It is a further object of the invention to reduce the processing time of the FWT computation to 2p clock cycles. It is another object of the invention to provide an FWT processor circuit which can be made up of any type of logic: device. It is also an object of the invention to configure an FWT processor with simplified control and interconnection lines, as compared to the prior art.